#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// int digui(int n) {
//     if(n==1) {
//         n=1;
//     }else {
//         return n*digui(n-1);
//     }
//     return n;
// }
// int main(void) {
//     // printf("Hello, World!\n");
//     // int a[10];
//     // srand((unsigned int)time(NULL));
//     // int sum=0;
//     // for (int i = 0; i < 10; ++i) {
//     //     a[i]=rand()%100+1;
//     //     printf("%d ",a[i]);
//     //     sum+=a[i]/10;
//     // }
//     // printf("\n%d\n",sum);
//     // for (int i = 0; i < 10; ++i) {
//     //     if(a[i]>sum) {
//     //         printf("%d ",a[i]);
//     //     }
//     // }
//     int n;
//     scanf("%d",&n);
//     printf("%d",digui(n));
//
//     return 0;
// }
// void removeChar(char *str, char ch) {
//     char *src,*dst;
//     src=str;
//     for (src=dst=str;*src!='\0';src++) {
//         if(*src!=ch) {
//             *dst++=*src;
//         }
//     }
//     *dst='\0';
// }
// int main() {
//     char str[] = "Hello, I am a ccccc C program.";
//     char ch = 'c';
//     printf("Original string: %s\n", str);
//     removeChar(str, ch);
//     printf("String after removing '%c': %s\n", ch, str);
//     return 0;
// }
// double mypow(double x,int y) {
//     int dig=1;
//     for (int i = 0; i < y; ++i) {
//         dig*=x;
//     }
//     return dig;
// }
// int main() {
//     int n;
//     double a;
//     scanf("%lf %d",&a,&n);
//     double x=mypow(a,n);
//     printf("%lf",x);
//     return 0;
// }

#include <stdio.h>

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i]; // 取出未排序部分的第一个元素
        j = i - 1;

        // 将大于key的元素向后移动一个位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // 将key插入到正确的位置
    }
}

// 打印数组的函数
void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 测试插入排序
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}